import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.ValueSource;

import java.util.Stack;

/**
 * 简化路径
 * 题目：以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
 * <p>
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
 * <p>
 * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
 * <p>
 * 示例 1：
 * 输入："/home/"
 * 输出："/home"
 * 解释：注意，最后一个目录名后面没有斜杠。
 * <p>
 * 示例 2：
 * 输入："/../"
 * 输出："/"
 * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
 * <p>
 * 示例 3：
 * 输入："/home//foo/"
 * 输出："/home/foo"
 * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
 * <p>
 * 示例 4：
 * 输入："/a/./b/../../c/"
 * 输出："/c"
 * <p>
 * 示例 5：
 * 输入："/a/../../b/../c//.//"
 * 输出："/c"
 * <p>
 * 示例 6：
 * 输入："/a//b////c/d//././/.."
 * 输出："/a/b/c"
 * <p>
 * 来源：力扣（LeetCode-71）
 * 链接：https://leetcode-cn.com/problems/simplify-path
 *
 * @author godfrey
 * @since 2020-10-28
 */
@DisplayName("简化路径")
public class SimplifyPath extends BaseTest {

    @DisplayName("利用栈-时间复杂度：O(n),空间复杂度：O(n)")
    @ParameterizedTest
    @ValueSource(strings = {"/home/", "/../", "/home//foo/", "/a/./b/../../c/", "/a/../../b/../c//.//", "/a//b////c/d//././/.."})
    void simplifyPath(String path) {
        //栈存储路径
        Stack<String> stack = new Stack<>();

        // 首先将字符串以 “/” 分隔存
        for (String s : path.split("/")) {
            // 如果访问到的是 “..” 则说明要返回上一级,要将当前元素出栈
            if ("..".equals(s)) {
                // 还需判断栈是否为空,否则会报错
                if (!stack.isEmpty()) {
                    stack.pop();
                }
                // 如果数组非空并且当前元素不是 “.” 说明当前元素是路径信息，要入栈
            } else if (!s.isEmpty() && !".".equals(s)) {
                stack.push(s);
            }
        }

        StringBuilder result = new StringBuilder();
        // 如果栈内没有元素说明没有路径信息，返回 “/” 即可
        if (stack.isEmpty()) {
            result.append('/');
        } else {
            for (final String s : stack) {
                result.append('/').append(s);
            }
        }
        System.out.println(result.toString());
    }
}
